﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target/
/*
题目描述：
给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。
返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。


示例 1：
输入: letters = ['c', 'f', 'j']，target = 'a'
输出: 'c'
解释：letters 中字典上比 'a' 大的最小字符是 'c'。

示例 2:
输入: letters = ['c','f','j'], target = 'c'
输出: 'f'
解释：letters 中字典顺序上大于 'c' 的最小字符是 'f'。

示例 3:
输入: letters = ['x','x','y','y'], target = 'z'
输出: 'x'
解释：letters 中没有一个字符在字典上大于 'z'，所以我们返回 letters[0]。
 

提示：
2 <= letters.length <= 104
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母
*/

// 方法1——直接遍历
/*
思路：
先定一个char变量ch，将其初始化为letters[0]。
然后遍历letters数组，第一次遇到letters[i] > target时，就就将letters[i]赋值给ch，
最后统一返回ch即可。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
char nextGreatestLetter1(char* letters, int lettersSize, char target) {
	assert(letters);
	char ch = letters[0];
	int i = 0;
	for (i = 0; i < lettersSize; i++) {
		if (letters[i] > target) {
			ch = letters[i];
			break;
		}
	}
	return ch;
}
// 时间复杂度：O(n)，n为数组长度，最坏情况下我们需要遍历完整个数组。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。

// 方法2——二分法——极限区间
/*
思路：
我们可以使区间一直缩小，在最后区间长度缩小为1时，判断left指向的元素是否大于target
如果大于，则left指向的元素就是大于target的最小字符。若不大于，则直接返回letters[0]。
当letters[mid] > target时，执行right = mid，使区间向左端逼近；
当letters[mid] < target时，执行left = mid + 1，使区间向右端逼近；
若是出现letters[mid] == target，我们依然是执行left = mid + 1，让区间向右端逼近。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
char nextGreatestLetter2(char* letters, int lettersSize, char target) {
	assert(letters);
	int left = 0;
	int right = lettersSize - 1;
	int mid = 0;
	while (left < right) {
		mid = left + ((right - left) >> 1);
		if (letters[mid] > target) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	return letters[left] > target ? letters[left] : letters[0];
}
// 时间复杂度：O(logn)，n为数组长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。





int main() {
	char letters[] = { 'e','e', 'g', 'g'};
	int len = sizeof(letters) / sizeof(letters[0]);
	printf( "% c\n", nextGreatestLetter2(letters, len, 'g'));
	return 0;
}